package 题目集.动态规划.背包问题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * 这题直接用多重背包会超时，正解可能是混合背包
 * 能成功找零的钱数种类 每一种货币都给定面值val[i]，和拥有的数量cnt[i] 想知道目前拥有的货币，在钱数为1、2、3…m时 能找零成功的钱数有多少
 * 也就是说当钱数的范围是1~m 返回这个范围上有多少可以找零成功的钱数 比如只有3元的货币，数量是5张 m = 10
 * 那么在1~10范围上，只有钱数是3、6、9时，可以成功找零 所以返回3表示有3种钱数可以找零成功。 测试链接
 * :http://poj.org/problem?id=1742
 */
public class ch10_能成功找零的钱数种类 {
	static int maxN = 101;
	static int maxN2 = maxN * 17;
	static int[] w = new int[maxN2];
	static int[] c = new int[maxN];

	public static void main(String[] args) {
		Reader sc = new Reader();
		while (true) {
			int n = sc.nextInt();
			int sum = sc.nextInt();
			if (n == 0)
				break;
			for (int i = 1; i <= n; i++) {
				w[i] = sc.nextInt();
			}
			for (int i = 1; i <= n; i++) {
				c[i] = sc.nextInt();
			}
			int cnt = n;
			for (int i = 1; i <= n; i++) {
				int count = c[i] - 1; // 1-n就是数量为1的每种货币
				for (int k = 2; k <= count; k = k << 1) {
					count -= k;
					w[++cnt] = k * w[i];
				}
				if (count > 0) {
					w[++cnt] = count * w[i];
				}
			}
			int res = dp(cnt, sum);
			System.out.println(res);
		}
	}

	public static int dp(int n, int sum) {
		boolean[][] dp = new boolean[2][sum + 1];
		int pre, cur = 0;
		dp[0][0]=true;
		for (int i = 1; i <= n; i++) {
			pre = cur;
			cur = (cur + 1) % 2;
			for (int j = 0; j <= sum; j++) {
				// 不要当前和要当前
				dp[cur][j] = dp[pre][j] || (j >= w[i] && dp[pre][j - w[i]]);
			}
		}
		dp[cur][0]=false;
		int ans = 0;
		for (boolean tag : dp[cur]) {
			ans += tag ? 1 : 0;
		}
		return ans;
	}

	static class Reader {
		private StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		public int nextInt() {
			try {
				in.nextToken();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return (int) in.nval;
		}
	}
}
